package org.example.myleet.p1018;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    /**
     * 4 ms
     * 取余运算法则
     * (a+b)%p = (a%p + b%p)%p
     * (a*b)%p = (a%p * b%p)%p
     * 令N[i]为第i个位置子序列代表的数字，令M[i]为Ni取余5的结果，M[i] = N[i] % 5
     * 推理可知N[i] = N[i-1]<<1 + A[i]，M[i] = (N[i-1]<<1 + A[i]) % 5
     * M[i] = ((N[i-1]<<1) % 5) + A[i] % 5) % 5
     * A[i]%5的结果还是A[i]
     * (N[i-1]<<1) % 5运用取余的乘法交换律得到((N[i-1]%5)<<1) % 5，而N[i-1]%5即是M[i-1]
     * 所以M[i] = (((M[i-1]<<1) % 5) + A[i]) % 5
     */
    public List<Boolean> prefixesDivBy5(int[] A) {
        List<Boolean> result = new ArrayList<>(A.length);
        int Ni = A[0];
        int Mi = Ni % 5;
        result.add(Mi == 0);
        for (int i=1; i<A.length; i++) {
            Mi = ((Mi<<1) % 5 + A[i]) % 5;
            result.add(Mi == 0);
        }
        return result;
    }
}
